#include <cmath>
#include <vector>

// reduce
template<typename T, typename F>
T reduce(T *begin, T *end, F f) {
	if (begin == end) return 0;
	T ans = *begin;
	for (T* i = ++begin; i != end; ++i)
		ans = f(ans, *i);
	return ans;
}
template<typename T, typename F>
T reduce(std::vector<T> v, F f) {
	if (v.size() < 1) return 0;
	T ans = v[0];
	for (typename std::vector<T>::iterator it = v.begin() + 1; it != v.end(); ++it)
		ans = f(ans, *it);
	return ans;
}

// range
template<typename T>
std::vector<T> range(T begin, T end, T step=1) {
	if (begin == end || (begin < end && step <= 0) || (begin > end && step >= 0))
		return std::vector<T>();
	std::vector<T> res;
	for (T i = begin; (i - step < end) == (i < end); i += step)
		res.push_back(i);
	if (res.size() > 2 && fabs(res[res.size() - 1] - end) < 1e-10) res.erase(res.end() - 1);
	return res;
}
template<typename T>
std::vector<T> range(T end) {
	T begin = 0, step = 1;
	if (begin == end || (begin < end && step <= 0) || (begin > end && step >= 0))
		return std::vector<T>();
	std::vector<T> res;
	for (T i = begin; (i - step < end) == (i < end); i += step)
		res.push_back(i);
	if (res.size() > 2 && fabs(res[res.size() - 1] - end) < 1e-10) res.erase(res.end() - 1);
	return res;
}

// map
template<typename T, typename F>
std::vector<T> map(std::vector<T> v, F f) {
	std::vector<T> res = v;
	for (typename std::vector<T>::iterator it = res.begin(); it != res.end(); ++it)
		*it = f(*it);
	return res;
}
